// Thor - High Performance C++ containers and algorithm library.
//
// Copyright (c) 2010 Su Shi. All rights reserved.
//
// Author: Su Shi <carmack.shi [at] gmail.com>

#ifndef THOR_GEOMETRY_H_
#define THOR_GEOMETRY_H_

#include <vector>
#include <set>
#include <functional>

namespace thor {

namespace geom {

struct Point2d {
double x;
double y;
};

struct Point3d {
double x;
double y;
double z;
};

typedef enum EventType_ {
  LOWER = 1,
  CROSSING = 2,
  UPPER = 4,
  ALL = LOWER | CROSSING | UPPER,
} EventType;

//struct EventPoint2d : public Point2d {
//  EventPoint2d(const Point2d& pt, EventType event_type)
//    : Point2d(pt), event_type_(event_type) { }
//  EventType event_type_;
//};

class Segment2d {
 public:
  Segment2d(const Point2d& start_pt, const Point2d& end_pt)
    : start_pt_(start_pt), end_pt_(end_pt),
      lower_x_(std::min(start_pt.x, end_pt.x)),
      lower_y_(std::min(start_pt.y, end_pt.y)),
      upper_x_(std::max(start_pt.x, end_pt.x)),
      upper_y_(std::max(start_pt.y, end_pt.y)) { }

  Point2d start_point() const { return start_pt_; }
  void set_start_point(const Point2d& start_pt) { start_pt_ = start_pt; }
  Point2d end_point() const { return end_pt_; }
  void set_end_point(const Point2d& end_pt) { end_pt_ = end_pt; }

  double lower_x() const { return lower_x_; }
  double lower_y() const { return lower_y_; }
  double upper_x() const { return upper_x_; }
  double upper_y() const { return upper_y_; }

  double Slope() const { return (upper_y_ - lower_y_) / (upper_x_ - lower_x_); }

  double EvaluateY(double coord_x) const {
    return lower_y_ + Slope() * (coord_x - lower_x_);
  }

 private:
  Point2d start_pt_;
  Point2d end_pt_;

  // Bounding Values for Segment2d.
  double lower_x_;
  double lower_y_;
  double upper_x_;
  double upper_y_;
};

//class LineSegment2d : public Segment2d {
// public:
//  LineSegment2d(const Point2d& start_pt, const Point2d& end_pt)
//    : Segment2d(start_pt, end_pt) { }
//};
//
//class CircularArc2d : public Segment2d {
// public:
//  CircularArc2d(const Point2d& start_pt,
//                const Point2d& mid_pt,
//                const Point2d& end_pt);
//
//  Point2d center() const { return center_; }
//  double radius() const { return radius_; }
//
// private:
//  Point2d mid_pt_;
//  double radius_;
//  Point2d center_;
//};

class MutableSegment2dSet;

class Segment2dCompare {
 public:
  Segment2dCompare(const MutableSegment2dSet& set)
    : set_(set) { }

  bool operator() (const Segment2d& lhs, const Segment2d& rhs) const;

 private:
  const MutableSegment2dSet& set_;
};


class MutableSegment2dSet {
 public:
  typedef std::set<Segment2d, Segment2dCompare> Segment2dSet;
  typedef Segment2dSet::iterator iterator;
  typedef Segment2dSet::const_iterator const_iterator;

  void SetScanPosition(double scan_poisition_x) { 
    scan_position_x_ = scan_poisition_x;
    Reorder();
  }
  double scan_position() const { return scan_position_x_; }

  // Some standard std::set member functions.
  iterator begin() { return set_.begin(); }
  iterator end() { return set_.end(); }
  const_iterator begin() const { return set_.begin(); }
  const_iterator end() const { return set_.end(); }

  std::pair<iterator, bool> insert(const Segment2d& segment) {
    return set_.insert(segment);
  }

  iterator find(const Segment2d& segment) {
    return set_.find(segment);
  }

 private:
  Segment2dSet set_;
  double scan_position_x_;

  // Iterator
  class MutableIterator : public Segment2dSet::iterator {
   public:
    typedef Segment2dSet::iterator BaseIterator;

    MutableIterator() { }
    MutableIterator(const BaseIterator& bi)
      : BaseIterator(bi) { }

    // Some iterator operatioins redefinement.
    Segment2d& operator*() {
      return const_cast<Segment2d&>(BaseIterator::operator*());
    }
    const Segment2d& operator*() const {
      return BaseIterator::operator*();
    }

    MutableIterator& operator++() {
      BaseIterator::operator++();
      return *this;
    }
    const MutableIterator operator++(int) {
      MutableIterator temp(*this);
      ++(*this);
      return temp;
    }

    MutableIterator& operator--() {
      BaseIterator::operator--();
      return *this;
    }
    const MutableIterator operator--(int) {
      MutableIterator temp(*this);
      --(*this);
      return temp;
    }
  };

  void Reorder();
  void Reverse(iterator first, iterator last);
  iterator GetIntersectingSegments(iterator first, iterator last);

};


// Intersection Definition:
//  Any pair of two segments share [1, 2] same points.
//    - shared end-points.
//    - shared internal point.
// Exception:
//  Overlapping part of two segments.
std::vector<Point2d> FindIntersections(const std::vector<Segment2d>& segments);

}  // geom

}  // thor

#endif  // THOR_GEOMETRY_H_